The present invention relates generally to a control process for expert systems, and, more particularly, to an expert system control process for resolving problems in time-constrained situations.
In certain applications, a significant need exists for expert systems which can operate to provide satisfactory decisions in critically time-constrained situations. This is often the case in military applications. Although the invention is certainly not limited to military applications, the following discussion will pertain to a military situation for purposes of example only. For example, in advanced avionics applications, it would be very desirable to have an intelligent system to assist pilots in making in-flight tactical decisions. In combat situations, pilots face severe workload stress in terms of the magnitude, diversity, and speed of the required decisions. Furthermore, pilots are overwhelmed by the quantity of incoming data and communications upon which they must base life-critical decisions.
Pilots are confronted with numerous dynamically changing situations, each of which requires precise activation of one of the dozens of switches, buttons, and knobs covering their controls. While each of the aircraft's hundreds of components and systems serve legitimate purposes, the technologies which created them have outpaced the technology for intelligently interfacing these systems to the pilot.
In order to support the next generation of advanced single-pilot helicopters and aircraft, the technology must be developed to provide intelligent information processing capabilities in the cockpit. These intelligent processing systems will off-load lower-level decision-making tasks from the pilot and provide tactical advisories in various situation assessment tasks. The resulting cockpit environments will be characterized by enhanced, efficient performance and reduced pilot workload.
Emerging techniques in knowledge-based expert systems are providing the solution to this dilemma by developing methods for representing and applying knowledge stored in a computer to solve problems that are generally thought to require significant human expertise (e.g. see Davis, R., "Expert Systems: Where Are We? And Where Do We Go From Here?", A.I. Magazine, Spring 1982, which is hereby incorporated by reference). These knowledge-based expert systems will complement the pilot's performance by off-loading lower-level tasks so that the pilot may concentrate on higher-level tactical and strategic objectives.
Although expert system technology has been evolving since the mid 1960's, the development of expert systems for time-constrained environments is still in its infancy. Referring to a military example, the real-time cockpit requirements for knowledge-based decision aids introduce several areas of expert system technology requiring further research and development. State-of-the-art expert systems have not yet confronted real-time constraints either in military situations or elsewhere. Typically, in the past, real-time performance and expert systems have not been considered in the same system.
An "expert system" is an intelligent computer program that uses knowledge and inference procedures to solve problems that are difficult enough to require significant human expertise. An expert system consists of:
(1) A knowledge base of domain facts and heuristics associated with the problem. The facts constitute a body of information that is widely shared, publicly available, and generally agreed upon by experts in a field. The "heuristics" are mostly private, little-discussed rules and strategies of good judgment, plausible reasoning, and good guessing that characterize expert-level decision-making and drastically limit search in large problem spaces. This knowledge is used by the system in reasoning about the problem. PA1 (2) A control structure for symbolically processing and utilizing the information stored in the knowledge base to solve the problem. This control structure is also commonly referred to as the inference engine. PA1 (3) A global data base to serve as a working memory to keep track of the problem status, input data, and relevant facts and history of the solution progression. PA1 (4) Explanation systems to allow the user to challenge and examine the reasoning process underlying the system's answers. This includes a user friendly interface to facilitate user interaction with the system. PA1 (5) Knowledge acquisition system to facilitate the addition of new knowledge into the system. Knowledge acquisition is an ongoing process, thus the knowledge must evolve over time through several iterations of trial and error. This interactive transfer of expertise from a human expert to the expert system is required in order to achieve an operationally acceptable level of performance. PA1 (1) forward-chained (data-driven) inferencing; and PA1 (2) backward-chained (goal-driven) inferencing.
The fundamental structure of an expert system is shown in FIG. 1. The major architectural distinction between a knowledge-based expert system and a conventional computer program is that an expert system maintains a clear, distinct separation between the general knowledge about the problem (knowledge base 10) and the reasoning mechanisms for symbolically applying this knowledge (control structure 12). Instead of being programmed to follow step-by-step procedures, an expert system employs a few general problem-solving procedures for symbolically applying knowledge and heuristics to find solutions to general classes of problems. As shown in FIG. 1, input data 16 is coupled to the control structure 12 and the knowledge base 10 through the global data base 14. A user interfaces with the expert system through the natural language interface 18.
Over the past decade, several Artificial Intelligence (A.I.) research groups have built highly specialized knowledge-based expert systems for a variety of domains (e.g. medicine, chemistry, geology, computer configurations, electronic fault diagnosis, etc.). The number of organizations developing expert systems has grown sharply over the past five years. Furthermore, research has rapidly spread and intensified in academia, spurred by this influx of industry and government funds. Researchers have recognized the potential applicability of expert systems for a wide variety of applications. However, this research still has not addressed the real-time constraints prevalent in military applications.
Previous university and industrial research activities addressing real-time constraints have focused on developing faster symbolic processing machines and multi-processing architectures (e.g. see Halstead, R. H., "Multilisp: A Language for Concurrent Symbolic Computation", MIT Labortory for Computer Science, August 1984, which is hereby incorporated by reference). Present-day expert systems claim real-time performance simply by virtue of their application domain being small enough not to require sophisticated processing. However, using conventional expert system inferencing techniques on these enhanced architectures will require that an upper bound be placed on the size of the knowledge base to ensure real-time processing. This upper limit on the size of a knowledge base is unacceptable for most military applications since the knowledge base is expected to grow and expand over time. The complexity of military scenarios and other complex situations mandates that a new generation of expert system inferencing techniques be developed to efficiently process these knowledge bases in real-time.
The present inventors have recognized that faster machines and limited domains do not satisfy the technology requirements for real-time expert systems. Accordingly, they have undertaken research to address the problem-solving paradigms that enable time-constrained decisions-making in complex situations.
Traditional expert system control strategies may fail to provide responses in time-stressed scenarios. Most expert system control strategies employ a depth-first search through a knowledge base in order to reach a decision. However, in a time-constrained environment such as that found in many military situations, this depth-first traversal is not guaranteed to achieve a reliable solution, or more importantly any solution at all.
An expert system control strategy contains the problem solving mechanisms for symbolically processing and utilizing the information stored in the knowledge base to solve problems. Two reasoning mechanisms are commonly used in expert systems, either alone or in combination, to process the knowledge base. These mechanisms are:
The specific implementation of a reasoning mechanism depends on the nature of the problem and the representation of the knowledge being manipulated.
When data or basic ideas serve as a starting point, then forward-chaining is the natural direction for the problem solution. In these data-driven inferencing systems, the system reasons forward from the facts to a solution by repeatedly evaluating the antecedents of all rules in the knowledge base until a steady-state condition is reached. However, these forward-chained systems may never terminate if the initial evidence does not lead to a conclusion. Thus, accordingly, most expert systems in practice tend to be goal-driven.
When a goal state or hypothesis serves as an initial focus point, then the inverses of inference rules are applied to find a path back to the initial state. In this goal-directed inferencing scheme, the system works backward from a hypothetical solution (goal) to find evidence supporting that goal. Backward-chaining is applicable to most diagnosis and planning problems.
This backward-chained inferencing strategy explores each potential hypothesis in order of likelihood. The system searches the knowledge base for a rule(s) whose consequent matches the desired conclusion. The system then attempts to recursively verify each resulting rule in turn until the antecedent part of the rule matches the initial problem description stored in the global data base. Each hypothesis is explored until all hypotheses have been exhausted. The system then ranks the hypotheses by the degree to which they are supported by the evidence and presents the resulting conclusion to the user.
The limitation, however, of this depth-first backward-chained inferencing strategy is that the evaluation of the knowledge base is independent of the amount of processing time available in the given scenario. In time-stressed scenarios, the system might inappropriately plunge depth-first into an insignificant path of reasoning and not achieve a solution within the bounded response time. Traditional expert system inferencing strategies contain no focusing mechanism to identify the most influential, cost-effective knowledge to evaluate in the knowledge base. Thus, these traditional inferencing strategies are inappropriate for time-constrained decision-making domains.